from typing import List

"""
1 表示起始方格。且只有一个起始方格。
2 表示结束方格，且只有一个结束方格。
0 表示我们可以走过的空方格。
-1 表示我们无法跨越的障碍。
"""


class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        # 计算一下多少行多少列
        R, C = len(grid), len(grid[0])

        def neighbors(r, c):
            for nr, nc in ((r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1)):
                if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] % 2 == 0:
                    yield nr, nc

        todo = 0
        # 遍历计算起始方块的位置和结束方块的位置
        for r, row in enumerate(grid):
            for c, val in enumerate(row):
                if val != -1: todo += 1
                if val == 1: sr, sc = r, c
                if val == 2: tr, tc = r, c

        self.ans = 0

        def dfs(r, c, todo):
            todo -= 1
            if todo < 0: return
            # 如果到达了终点，并且 走遍了所有的格子。可选路径加一
            if r == tr and c == tc:
                if todo == 0:
                    self.ans += 1
                return
            # 标记一下，已经通过
            grid[r][c] = -1
            # 向四周扩散，深度优先遍历
            for nr, nc in neighbors(r, c):
                dfs(nr, nc, todo)
            # 遇到四周无可用节点后，标记当前节点为普通节点
            grid[r][c] = 0

        dfs(sr, sc, todo)
        return self.ans


if __name__ == '__main__':
    grid = [[1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 2, -1]]
    solution = Solution()
    print(solution.uniquePathsIII(grid))
